package set;

import org.junit.Test;

import java.util.*;

public class PermutationII47 {

    @Test
    public void test() {
        permuteUnique(new int[]{1});
        permuteUnique(new int[]{1, 2, 2, 3});
        permuteUnique(new int[]{1, 2, 2, 2, 3});
        permuteUnique(new int[]{1, 1, 2, 2});
        permuteUnique(new int[]{1, 1, 2, 2, 3});
    }

    // 不能直接用46的递进交换法(循环的杂度为n!)了, 因为不同的交换路径可能导致相同的结果
    // 例如: 对于n={1, 1, 2, 2}, swap(n, 1, 3) 与 swap(n, 1, 2)+swap(n, 2, 3) 的结果相同, 都是{1, 2, 2, 1}
    // 因此需要用线性选择法(循环地复杂度为n^n), 并且用需要记录是否已经访问.
    // 记录是否已访问的方法: (1) 用set(不行); (2) 对数组排序, 然后用visited[i-1]和n[i]是否等于n[i-1]来判断
    public List<List<Integer>> permuteUnique(int[] n) {
        int count = 1;
        for (int i = 1; i <= n.length; i++) {
            count *= i;
        }
        List<List<Integer>> results = new ArrayList<>(count);

        Arrays.sort(n);

        boolean[] visited = new boolean[n.length];
        Arrays.fill(visited, false);

        List<Integer> result = new ArrayList<>(n.length);
        permuteRecursively(n, visited, result, results);
        System.out.println(results.size());


        for (List<Integer> r: results) {
            System.out.println(r);
        }
        System.out.println();
        return results;
    }

    public void permuteRecursively(int[] n, boolean[] visited, List<Integer> result, List<List<Integer>> results) {
        if (result.size() == n.length) {
            results.add(new ArrayList<>(result));
            return;
        }

        // 不能再从k开始了, 要从0开始
        for (int i = 0; i < n.length; i++) {
            // n[i]已经被取过了
            if (visited[i]) {
                continue;
            }

            // n[i]没有被取过. 但n[i-1]与n[i]相等, 而且n[i-1]当前也没有被取过, 说明n[i-1]以前被取到过了, 会重复, 要避免
            if (i > 0 && n[i] == n[i-1] && !visited[i-1]) {
                continue;
            }

            result.add(n[i]);
            visited[i] = true;
            permuteRecursively(n, visited, result, results);
            result.remove(result.size()-1);
            visited[i] = false;
        }
    }
}
